package main.Q801_900;

import java.util.*;

public class Q881_890 {
    public static void main(String[] args) {
        System.out.println("Question881：");
        System.out.println("Question882：");
        System.out.println("Question883：");
        System.out.println("Question884：");
        System.out.println("Question885：螺旋矩阵 III");
        System.out.println("Question886：");
        System.out.println("Question887：");
        System.out.println("Question888：");
        System.out.println("Question889：根据前序和后序遍历构造二叉树");
        System.out.println("Question890：查找和替换模式");
    }
}

class Question885 {
    public int[][] spiralMatrixIII(int rows, int cols, int rStart, int cStart) {
        int[][] result = new int[rows * cols][2];
        int[][] around = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int x = rStart, y = cStart, num = 1, dir = 0;  //{x, y}为当前位置，num为当前查找的数字，dir为当前的方向
        int Left = cStart - 1, Right = cStart + 1, Upper = rStart - 1, Bottom = rStart + 1;  //四个方向的边界
        while (num <= rows * cols) {
            if (x >= 0 && x < rows && y >= 0 && y < cols) {  //{x， y}位置在矩阵中
                result[num - 1] = new int[]{x, y};
                num++;
            }
            if (dir == 0 && y == Right) {  //向右到右边界
                dir += 1;  //调转方向向下
                Right += 1;  //右边界右移
            } else if (dir == 1 && x == Bottom) {  //向下到底边界
                dir += 1;
                Bottom += 1;  //底边界下移
            } else if (dir == 2 && y == Left) {  //向左到左边界
                dir += 1;
                Left--;  //左边界左移
            } else if (dir == 3 && x == Upper) {  //向上到上边界
                dir = 0;
                Upper--;  //上边界上移
            }
            x += around[dir][0];   //下一个节点
            y += around[dir][1];
        }
        return result;
    }
}

class Question889 {
    public TreeNode constructFromPrePost(int[] pre, int[] post) {
        if (pre == null || pre.length == 0) {
            return null;
        }
        return process(pre, post);
    }

    private TreeNode process(int[] pre, int[] post) {
        if (pre == null || pre.length == 0) {
            return null;
        }
        //数组长度为1时，直接返回即可
        if (pre.length == 1) {
            return new TreeNode(pre[0]);
        }
        //根据前序数组的第一个元素，创建根节点
        TreeNode root = new TreeNode(pre[0]);
        int n = pre.length;
        for (int i = 0; i < post.length; ++i) {
            if (pre[1] == post[i]) {
                //根据前序数组第二个元素，确定后序数组左子树范围
                int left_count = i + 1;
                //拆分前序和后序数组，分成四份
                int[] pre_left = Arrays.copyOfRange(pre, 1, left_count + 1);
                int[] pre_right = Arrays.copyOfRange(pre, left_count + 1, n);
                int[] post_left = Arrays.copyOfRange(post, 0, left_count);
                int[] post_right = Arrays.copyOfRange(post, left_count, n - 1);
                //递归执行前序数组左边、后序数组左边
                root.left = process(pre_left, post_left);
                //递归执行前序数组右边、后序数组右边
                root.right = process(pre_right, post_right);
                break;
            }
        }
        //返回根节点
        return root;
    }
}

class Question890 {
    public boolean process(String s, String pat) {
        if (s.length() != pat.length()) return false;
        Map<Character, Character> map1 = new HashMap<>(), map2 = new HashMap<>();
        char[] str = s.toCharArray(), sp = pat.toCharArray();
        for (int i = 0; i < str.length; i++) {
            if (!map1.containsKey(str[i])) map1.put(str[i], sp[i]);
            if (!map2.containsKey(sp[i])) map2.put(sp[i], str[i]);
            if (map1.containsKey(str[i]) && map1.get(str[i]) != sp[i]) return false;
            else if (map2.containsKey(sp[i]) && map2.get(sp[i]) != str[i]) return false;
        }
        return true;
    }

    public List<String> findAndReplacePattern(String[] words, String pattern) {
        List<String> list = new ArrayList<>();
        for (String str : words) {
            if (process(str, pattern)) {
                list.add(str);
            }
        }
        return list;
    }
}